Recent years have seen considerable advancement in the use of computers to form pictures. Somewhat more specifically, the field of computer graphics involves the generation, representation, manipulation, processing, and evaluation of graphic objects with computers. Graphic objects created with the aid of a computer may or may not have an existing physical form. That is, using the techniques of computer graphics, pictures or graphic objects may be created without physical models, pictures, or drawings as those terms apply in a traditional sense. For example, a graphic object may be defined by a computer in terms of an abstract description (model) that can be transformed into a corresponding picture on a display surface as the face of a cathode ray tube.
Using computer graphics, displayed pictures typically are generated by manipulating or modifying mathematical representations of primitive geometrical shapes. That is, desired images may be created by processing primitive shapes such as squares and triangles with operations as those called "union" or "intersection". For example, a primitive shape of a house may be created by adding a triangle (representative of a roof) to a square (representative of walls). More complex images require the use of shapes with more complex curves and surfaces.
A person interacting with a computer may provide data (either directly or from the computer's memory) sufficient to specify a primitive image for display on a screen. That image then may be enhanced to a desired form by processing the basic data. In that regard, techniques and structures have been proposed for creating smooth appearing images in graphic displays. For example, see an article in Scientific American, September 1984, entitled "Computer Software for Graphics". With continuing work in the field of computer graphics, a persistent need has been revealed for structures to expedite and simplify the creation of desired images.
Somewhat recently, mathematical science has recognized the feasibility of using combinations of parametric patches as curved primitives to create graphic images. Such combinations of patches may be used to form complex images, much as a collection of cloth patches are joined to form a quilted bedspread. Patches provide flexibility and can represent both planar and curved surfaces. They can be generated by the parameterization of certain rational polynomial functions. Such techniques have been treated in the literature. For example, see INTERACTIVE COMPUTER GRAPHICS by Wolfgang K. Giloi, 1978, Prentice-Hall, Inc., specifically Chapter 4 entitled "Interpolation and Approximation of Curves and Surfaces"; GEOMETRIC PRINCIPLES AND PROCEDURES FOR COMPUTER GRAPHIC APPLICATIONS by Sylvan H. Chasen, 1978, Prentice-Hall, Inc., see Chapter 2, "Creating a Mathematical Formulation to Match Constraints"; and COMPUTATIONAL GEOMETRY FOR DESIGN AND MANUFACTURE by I. D. Faux and M. J. Pratt, John Wiley & Son, 1979, see Chapter 7, "Composite Surfaces".
One approach utilizing parametric patches is based on a method developed by Bezier and is described in the above texts. A polyhedron, e.g. rectangle, is used to outline a desired surface. The vertices of the polyhedron thus control the shape of the generated patch. The vertices are known as control points. Note that the control points at the corners of the patch lie on the polyhedron.
Parametric patch techniques are well suited for interactive computer graphics because a user may control the shape of patches simply by altering the position or the number of control points. Generally, a rough approximation of a desired surface can be accomplished by a user defining some initial control points. By subdividing a patch of a rough approximation into subpatches the image can be refined. As a technique, patch subdivision is treated in a book PRINCIPLES OF INTERACTIVE COMPUTER GRAPHICS by Newman and Sproull, 2nd Edition, 1979, McGraw-Hill, Inc., and in an article, "An Algorithm and Data Structure for 3D Object Synthesis Using Surface Patch Intersections", by Wayne E. Carlson appearing in Computer Graphics, July 1982, Vol. 16, No. 3 (ACMO-89791-076-1/82/007/0255).
Subdivision in this context is any process which exactly converts a parametric patch to several smaller ones. A number of control points for an initial patch are employed in well known equations for computing a similar number of control points for each subpatch. Thus, subdivision of a patch is accomplished by computing the coordinates of additional control points to further shape the surface as defined by subpatches. The motivation for subdivision is that progressive subdivision produces subpatches with control points that are progressively closer to the desired surface.
It has been proposed to perform patch subdivision on a general purpose computer. However, that approach is relatively slow and is not generally suitable for interactive computer use. Essentially, a need exists for an economical system to rapidly compute the coordinates for control points in the subdivision of parametric patches. The related apparatus for providing working data and for displaying resulting data is complex and voluminous but well known in the prior art. Accordingly, the system hereof is described in the form of a component. The place and use of the component in a composite computer graphics system will be readily apparent to persons of ordinary skill in the art.
In general, the system of the present invention operates in cooperation with a host computer. Signals are received from the host computer representative of initial control points definitive of a parametric patch. A plurality of parallel processors receive the control points simultaneously. In accordance with one disclosed embodiment, the signals representative of the control points are provided in a so-called "canonical" sequence which indicates the positional relationship of the control points. In this embodiment, a counter identifies the control points. In another disclosed embodiment, a name in the form of a single integer value is assigned to identify each control point.
As disclosed herein, each of the parallel subdivision processors may receive signals representative of control points to compute the coordinates of a distinct subpatch control point. However, in an alternative embodiment as disclosed herein, subdivision processors compute the coordinates of multiple control points.
Once a level of subdivision is completed, the subpatch control points are received by the host computer and stored. In that regard, the total processing time involves the intervals required to output the initial patch control points to the subdivision processors, during which time the computation of subpatch control points occurs, plus the intervals to input and store the subpatch control points into the host computer. The process is recursive so that further levels of subdivision expeditiously lead to greater refinement of the generated image.